Arithmetic coding is used in modern image and video encoders to improve coding efficiency. For example, the International Organization for Standardization/International Electrotechnical Commission (ISO/IEC) Moving Picture Experts Group-4 (MPEG-4) Part 10 Advanced Video Coding (AVC) Standard/International Telecommunication Union, Telecommunication Sector (ITU-T) H.264 Recommendation (hereinafter interchangeably the “MPEG-4 AVC Standard” or “H.264”) and the Joint Photographics Experts Group (JPEG) 2000 Standard (hereinafter “JPEG 2000 Standard”) employ adaptive binary arithmetic coding in which the probability of a symbol is updated after encoding the symbol. The probability update step makes the coding process adaptive to the video content. These update functions are tabulated in the standards.
Usually, adaptation of the probability of a symbol in a binary arithmetic coder is implemented by means of a look-up table. This can be costly in terms of memory usage. Moreover, the number of probabilities is limited.
An explicit update function solves some of these problems, but has its own limitations. First, a fast and efficient implementation has to be an integer implementation, but in this case, the degree of adaptation is very limited. That is, the adaptation rate is very coarse. Second, the probability can get very close to “0” or “1”, which is a problem because if the probability of a symbol is very close to “0” and the symbol appears, then its encoding cost is very high.
The MPEG-4 AVC Standard uses one of the two following entropy codecs depending on the profile: context-adaptive variable length coding (CAVLC); or context-adaptive binary arithmetic coding (CABAC). CABAC is based on arithmetic coding, which allows the assignment of a non-integer number of bits to each symbol of an alphabet, which is extremely beneficial for symbol probabilities that are greater than 0.5. This is not possible in CAVLC. On the other hand, the use of adaptive codes permits the adaptation to non-stationary symbol statistics. Another property of CABAC is the context modeling. The statistics of already coded syntax elements are used to estimate conditional probabilities. These conditional probabilities are used for switching several estimated probability models.
In the MPEG-4 AVC Standard, the arithmetic coding core engine and its associated probability estimation are specified as multiplication-free low-complexity methods using only shifts and table look-ups. The MPEG-4 AVC Standard relies on the assumption that the estimated probabilities of each context model can be represented by a sufficiently limited set of representative values. CABAC uses 64 representative probability values between 0.01875 and 0.5 for the least probable symbol (LPS). The values are derived from the following recursive equation:pn=αpn-1, for n=1, . . . , 63where p0=0.5 and α=0.9492.
As a result of this design, each context model in CABAC is determined by the following two parameters: its current estimate of the LPS probability, which in turn is characterized by an index n between 0 and 63; and its value of the most probable symbol (MPS) being either 0 or 1. Thus, the probability estimation is performed using a total number of 128 states, each of them represented by a 7-bit integer value. A look-up table holds the information of the states and how to jump from one state to another state given the input symbol. Note that the transition update function in the table is an approximation of an exponential function.
In the JPEG 2000 Standard, an adaptive binary arithmetic coder is used. The update function is tabulated. The table has 47 entries divided into two parts. The first 14 entries correspond to the “start-up” portion of the transition table, where few symbols have been observed. The remaining entries represent the non-transient portion of the table. Each entry includes the probability of the LPS to be used by the arithmetic coder, the next entry in the table to jump to in the case that the current symbol is the LPS or the MPS, and a fourth value that holds a 1 if the symbols associated with the LPS and MPS are to be exchanged.
The table in the JPEG 2000 Standard reflects a limited version of a scaled count estimator of the probability. This probability estimation is simply as follows:
  p  =                    C        0            +      Δ                      C        0            +              C        1            +              2        ⁢                                  ⁢        Δ            where p is the estimated probably, C0 is the count of symbol 0, C1 is the count of symbol 1, and Δ reflects a conservative policy in which highly skewed distributions are avoided until a large number of outcomes have been observed.
CABAC and JPEG 2000 rely on a finite state machine (FSM) for estimation of the probability of the output of a binary source. Transitions for the finite state machine are defined by a table stored in memory. A disadvantage of this approach includes the frequent referencing to this table (one time for every binary symbol encoding), which is critical for digital signal processing (DSP) implementations. Another disadvantage of this approach is that the tables are small due to memory limitations, so the number of possible probabilities is limited. Moreover, another disadvantage of this approach is that all the symbols have to be encoded with the same function/table, but the statistics and variability of different symbols may be different thus requiring different adaptation rates that a single table cannot offer. There is the option of using more than one table, but each additional table incurs extra complexity and requires additional memory.
A first prior art approach has proposed the use of an explicit probability update function to avoid the use of the table. In further detail, the first prior art approach proposes an adaptation procedure that explicitly uses an exponential update function. The function weights the previous observations with the new symbol as follows:pn=αpn-1+(1−α)sn  (1)where sn is the new symbol.
This function is a “sliding window”, since the newer observations have more weight than the older ones, thus adapting to the newer statistics. Parameter α is between 0 and 1 and controls the memory of the system. The closer to 0 the value of parameter α, the less memory it has, i.e., more weight is given to the newer symbols.
The update in Equation (1) can be efficiently implemented in integer arithmetic. The feasibility of integer arithmetic implementations is quite significant. For example, assume that the probability is (not normalized and is) a number between 0 and 216-1, using 16-bit arithmetic. Then, Equation (1) can be implemented as follows:pn=pn-1−(pn-1−sn216)>>m  (2)where parameter m controls the memory of the system (like parameter α in Equation (1)). The symbol “>>” means a right-shifting of the bits. The bits are right-shifted m positions. This operation is similar to divide by 2m.
Parameters m and α play the same role in Equation (1) and Equation (2), respectively. They are the memory rate of the update function, that is, they control the weight given to the past probability estimation and to the current symbols in the probability estimation. The closer to 0 the value of parameter α, the less memory the estimation has, i.e., more weight is given to the newer symbols. Similarly, the smaller m is, the more weight is given to the newer symbols, and the larger m is, the more weight is given to the previous estimation (and older symbols). Typically, m has a value from 3 to 7. In this case, pn indicates the probability of symbol 1 at observation number n. Note that this is arbitrary (a convention used here): pn could also indicate the probability of symbol 0.
This approach solves some of the problems of the prior art, but has its own limitations. One limitation of the first prior art approach is that the degree of adaptation is very limited by parameter m, which basically accounts for very coarse adaptation factors of the form of powers of 2. Another limitation of the first prior art approach is that the probability can get very close to 0 or 1, which is a problem because if the probability of a symbol is very close to 0 and the symbol appears, then it is very costly to encode the symbol.